﻿#include <iostream>
#include <string>

using namespace std;

/* 
	Problem is, find the longest palindromatic substring of a string
	This is a classic DP problem that is solved using a O(N^2) time with O(N^2) space.

	Here is the link to the problem: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-i.html,
	in which there is O(N^2) time and O(1) space solution introduced.

	This is the DP approach. Stated more formally below:
	Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

	Therefore,
	P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

	The base cases are:
	P[ i, i ] ← true
	P[ i, i+1 ] ← ( Si = Si+1 )

	This yields a straight forward DP solution, which we first initialize 
	the one and two letters palindromes, and work our way up finding all three 
	letters palindromes, and so on… 

	This gives us a run time complexity of O(N2) and uses O(N2) space to store the table.

	There is another O(N) solution posted at following links.
	http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

	Here is the link to the Chinese version of explanation:
	http://www.felix021.com/blog/read.php?2040
*/

string LongestPalindromeDP(string s) 
{  
    int n = s.length();  
    int longestBegin = 0;  
    int maxLen = 1;  
    bool table[1000][1000] = {false};  

    if (s.length() == 0 || s.length() == 1)
        return s;

    for (int i = 0; i < n; i++) 
    {   
        table[i][i] = true;  
    }  
    for (int i = 0; i < n-1; i++) 
    { 
        if (s[i] == s[i+1]) 
        { 
            table[i][i+1] = true;    
            longestBegin = i;      
            maxLen = 2;  
        }
    } 
    for (int len = 3; len <= n; len++) 
    {
        for (int i = 0; i < n-len+1; i++) 
        { 
            int j = i+len-1;     
            if (s[i] == s[j] && table[i+1][j-1]) 
            { 
                table[i][j] = true;  
                // I modified this part of code from LeetCode
                if (maxLen < len)
                {
                    longestBegin = i;    
                    maxLen = len;    
                }
            }
        }
    }
    
    return s.substr(longestBegin, maxLen);
}

int main()
{
    string s1 = "abba";
	string lps = LongestPalindromeDP(s1);
    cout << "The longest palidromatic string for "+s1+" is: " + lps << endl;

    string s2 = "aaabbaaabbaaaa";
	lps = LongestPalindromeDP(s2);
    cout << "The longest palidromatic string for "+s2+" is: " + lps << endl;

    cout<<"Press any key to terminate..."<<endl;

    return getchar();
}